package com.lz.learning;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 猜想
 */
public class Thinking {

    public static void main(String[] args) {
        Thinking thinking = new Thinking();
//        thinking.permute(new int[]{1, 2, 3});
        Queeu queeu = thinking.new Queeu();
        long l = System.currentTimeMillis();
        thinking.solveNQueens(10);
        long l1 = System.currentTimeMillis();
        queeu.solveNQueens(10);

        long l2 = System.currentTimeMillis();
        System.out.println(l1 - l);
        System.out.println(l2 - l1);


        String multiply = thinking.multiply("11", "11");
        System.out.println(multiply);
    }


    /**
     * 回溯测试
     * 全排列 1、2、3组成的数
     */
    List<List<Integer>> res = new LinkedList<>();

    List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        System.out.println(res);
        return res;
    }

    private void backtrack(int[] nums, LinkedList<Integer> track) {
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (track.contains(num)) continue;
            track.add(num);
            backtrack(nums, track);
            track.remove();
        }
        if (track.size() == nums.length)
            res.add(new ArrayList<>(track));
    }


    /**
     * 皇后问题回溯法，只能暴力解决
     */
    List<List<Integer>> board = new ArrayList<>();
    List<List<List<Integer>>> pos = new ArrayList<>();
    int n;

    List<List<List<Integer>>> solveNQueens(int n) {
        this.n = n;
        for (int i = 0; i < n; i++) {
            LinkedList<Integer> objects = new LinkedList<>();
            for (int j = 0; j < n; j++) {
                objects.add(-1);
            }
            board.add(objects);
        }
        backtrack(board, 0);
        printf(pos);
        return pos;
    }

    private void backtrack(List<List<Integer>> board, int row) {
        // 触发结束条件
        if (row == n) {
            pos.add(deepcopy(board));
            return;
        }
        for (int column = 0; column < n; column++) {
            //
            boolean isValid = isValid(board, row, column);
            if (isValid) {
                List<Integer> integers = board.get(row);
                integers.set(column, 1);
                backtrack(board, row + 1);
                integers.set(column, -1);
            }
        }
    }

    private boolean isValid(List<List<Integer>> board, int row, int column) {

        for (int i1 = 0; i1 < n; i1++) {

            List<Integer> integers = board.get(i1);

            if (i1 == row) {
                for (int i2 = 0; i2 < integers.size(); i2++) {
                    if (integers.get(i2) == 1) return false;
                }
            }

            if (integers.get(column) == 1) return false;

            int i2 = i1 + column - row;
            if (i2 < n && i2 >= 0 && integers.get(i2) == 1) return false;
            int i3 = -i1 + row + column;
            if (i3 >= 0 && i3 < n && integers.get(i3) == 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 辅助函数
     *
     * @param lists
     * @return
     */
    List<List<Integer>> deepcopy(List<List<Integer>> lists) {
        int size = lists.size();
        List<List<Integer>> list0 = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            List<Integer> objects = new ArrayList<>();
            List<Integer> integers = lists.get(i);
            for (int j = 0; j < size; j++) {
                objects.add(integers.get(j));
            }
            list0.add(objects);

        }
        return list0;
    }

    void printf(List<List<List<Integer>>> lists) {
        int size = lists.size();
        int k = 0;
        List<List<Integer>> list0 = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            List<List<Integer>> integers = lists.get(i);
            System.err.printf("\nindex:  %d\n", k++);
            for (int j = 0; j < integers.size(); j++) {
                List<Integer> integers1 = integers.get(j);
                System.out.println(integers1);
            }
        }
    }

    /**
     * 基于数组的实现
     */
    class Queeu {
        //        List<List<Integer>> board = new ArrayList<>();
        int[][] board;
        List<int[][]> pos = new ArrayList<>();
        int n;

        List<int[][]> solveNQueens(int n) {
            if (n == 0) return null;
            this.n = n;
            board = new int[n][n];
            backtrack(0);
            printf(pos);
            return pos;
        }

        private void backtrack(int row) {
            // 触发结束条件
            if (row == n) {
                pos.add(deepcopy(board));
                return;
            }
            for (int col = 0; col < n; col++) {
                //
                boolean isValid = isValid(row, col);
                if (isValid) {
                    int[] integers = board[row];
                    integers[col] = 1;
                    backtrack(row + 1);
                    integers[col] = 0;
                }
            }
        }

        private boolean isValid(int row, int col) {
            for (int i = 0; i < n; i++) {
                int[] integers = board[i];
                if (i == row) {
                    for (int i2 = 0; i2 < integers.length; i2++) {
                        if (integers[i2] == 1) return false;
                    }
                }
                if (integers[col] == 1) return false;

                int j1 = i + col - row;
                if (j1 < n && j1 >= 0 && integers[j1] == 1) return false;
                int j2 = -i + row + col;
                if (j2 >= 0 && j2 < n && integers[j2] == 1) return false;

            }
            return true;
        }


        /**
         * 辅助函数
         *
         * @param lists
         */
        void printf(List<int[][]> lists) {
            int size = lists.size();
            int k = 0;
            for (int i = 0; i < size; i++) {
                int[][] integers = lists.get(i);

                System.out.printf("\nindex:  %d\n", k++);
                for (int j = 0; j < integers.length; j++) {
                    int[] integers1 = integers[j];
                    for (int i1 : integers1) {
                        System.out.print(i1);

                    }
                    System.out.println();
                }
            }
        }

        int[][] deepcopy(int[][] lists) {
            int size = lists.length;
            int[][] ints = new int[size][size];
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    ints[i][j] = lists[i][j];
                }
            }
            return ints;
        }
    }

    /**
     * big数
     * 字符串相乘
     * @param s1
     * @param s2
     * @return
     */
    String multiply(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        char[] num1 = s1.toCharArray();
        char[] num2 = s2.toCharArray();
        // 结果最多为 m + n 位数
        int[] res = new int[m + n];
        // 从个位数开始逐位相乘
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1[i] - '0') * (num2[j] - '0');

                // 乘积在 res 对应的索引位置
                int p1 = i + j, p2 = i + j + 1;
                // 叠加到 res 上
                int sum = mul + res[p2];
                res[p2] = sum % 10;
                res[p1] += sum / 10;
            }
        // 结果前缀可能存的 0（未使用的位）
        int i = 0;
        while (i < res.length && res[i] == 0)
            i++;
        // 将计算结果转化成字符串
        StringBuilder str = new StringBuilder();
        for (; i < res.length; i++)
            str.append(res[i]);


        return str.length() == 0 ? "0" : str.toString();
    }
}
